Context Free Language

L = $0^n1^n$ is not regular
However, it is a Context Free Language

This means:

Context Free Grammar

A collection of substitution rules also called 'productions'

Has 'Variables' & 'Terminals'  
	 LHS 		&  RHS  
	 capital let   can be variables and symbols

The following grammar has only one variable (S)
- S is also the start variable
- Each rule specifies that the variable on the left can be replaced with
Example: Language of strings of form L = $0^n1^n$
- S -> 0 S 1
- S -> $\varepsilon$
- $0^n1^n | n = 3$: Fill in s until it's like 000 $\varepsilon$ 111
  - 0S1->00S11->000S111->000 $\varepsilon$ 111=000111

A 4 tuple $(V,\Sigma, R, S)$

V is a finite set called variables
$\Sigma$ is a finite set, disjoint form v called terminals
R is the finite set of rules of form
A -> w when A $\in$ V and w $\in$(V $\cup \Sigma$)$^\star$
S $\in$ V is the start variable

22 | A
Terminals | Rest of Rule

At each step expand the left most derivation
Eg: Rule B->ASAXBA
- match top of stack to a rule
- push right hand side of the rool onto stack
- pop stack

$\Sigma$={0,1,2}
S -> BS | A
A -> 0A | e
B -> BB1 | 2